package com.wj.algorithm.lintcode;


public class P59 {
    //    //target中储存的是元素的下标；规则是下标元素对应的距离，从大到小
    //    private void resort(int[] target, int[] distanceArray) {
    //        for(int i = 0, len = target.length; i < len; i ++) {
    //            int currentIndexDistance = distanceArray[target[i]];
    //            int currentDistanceIndex = i;
    //            for(int j = i + 1; j < len; j ++) {
    //                if(distanceArray[target[j]] > currentIndexDistance) {//找到一个比当前值大的
    //                    currentIndexDistance = distanceArray[target[j]];
    //                    currentDistanceIndex = j;
    //                }
    //            }
    //            if(currentDistanceIndex > i) {//交换
    //                int iValue = target[i];
    //                target[i] = target[currentDistanceIndex];
    //                target[currentDistanceIndex] = iValue;
    //            }
    //        }
    //    }
    //    
    //    private void resortIndexArrayAndCompareWith(int[] target, int[] distanceArray, int currentIndex) {
    //        if(currentIndex >= 0) {
    //            //交换
    //            int distance = distanceArray[currentIndex];
    //            if(distance < distanceArray[target[0]]) {
    //                target[0] = currentIndex;
    //                //替换之后再进行一次排序
    //                resort(target, distanceArray);
    //            }
    //        }
    //    }
    //    
    //    public int threeSumClosest(int[] numbers, int target) {
    //        if(numbers == null) {
    //            return 0;
    //        }
    //        int len = numbers.length;
    //        if(len <= 3) {
    //            return sumArray(numbers);
    //        }
    //
    //        //记录距离，绝对值
    //        int[] distance = new int[len];
    //        for(int i = 0; i < len; i ++) {
    //            int v = numbers[i];
    //            v = target - v; //Math.abs(target - v);
    //            distance[i] = v;
    //        }
    //        
    //        //距离最近的三个下标；对应距离最大的元素的下标排在前面
    //        //numbers中下标为i的元素，i储存在bottom3IndexArray中，距离储存在distance中
    //        //按照bottom3IndexArray的定义；距离最大的下标储存在bottom3IndexArray[0]，对应距离是distance[bottom3IndexArray[0]]
    //        int[] bottom3IndexArray = new int[3];
    //        
    //        int count = 0;
    //        for(int i = 0; i < len; i ++) {
    //            if(count < 3) {//不足三个
    //                bottom3IndexArray[count] = i;
    //                count ++;
    //            } else {
    //                //先进行一次排序
    //                resort(bottom3IndexArray, distance);
    //                resortIndexArrayAndCompareWith(bottom3IndexArray, distance, i);
    //            }
    //        }
    //        
    //        int sum = 0;
    //        for(int index : bottom3IndexArray) {
    //            sum += numbers[index];
    //        }
    //        
    //        return sum;
    //        }

    private int sumArray(int[] arr) {
        int sum = 0;
        for (int i : arr) {
            sum += i;
        }
        return sum;
    }
    
    public int threeSumClosest(int[] numbers, int target) {
        if (numbers == null) {
            return 0;
        }
        int len = numbers.length;
        if (len <= 3) {
            return sumArray(numbers);
        }

        int sum = 0;
        int minDistance = Integer.MAX_VALUE;
        int index = 0;
        int i = 0, j = 0;
        
        //循环遍历终止指针
        int iStart = -1;
        //某一个遍历，保存的最小距离
        int tempMinDis = Integer.MAX_VALUE;
        //某一个遍历，最小距离对应的和
        int tempSum = 0;
        while(true) {
            
            if(i == iStart) {//是否遍历了一圈
                if(tempMinDis < Integer.MAX_VALUE) {//如果遍历了一圈，而且有最小距离
                    if(tempMinDis < minDistance) {
                        minDistance = tempMinDis;
                        sum = tempSum;
                        //重置最小距离临时变量
                        tempMinDis = Integer.MAX_VALUE;
                    }
                    index ++;
                }
                //重置终止指针
                iStart = -1;
            }
            //i==index，则下一轮
            if(i == index) {
                i ++;
                continue;
            }
            if(iStart == -1) {//记录某一次循环的开始指针位置
                iStart = i;
            }
            j = i + 1;
            while(j < len) {

                int ts = numbers[i] + numbers[j];
                
                if(j != index) {//j不等于index的情况
                    if(Math.abs(numbers[index] + ts - target) < tempMinDis) {
                        tempMinDis = Math.abs(numbers[index] + ts - target);
                        tempSum = numbers[index] + ts;
                    }
                }
                j ++;
            }
            i ++;
            if(i >= len) {
                i = 0;
            }
            //跳出逻辑
            if(index >= len) {
                break;
            }
        }
        
        return sum;
    }

    public static void main(String[] args) {
        System.out.println(new P59().threeSumClosest(new int[] { -2, -3, -4, -5, -100, 99, 1, 4, 4, 4, 5, 1, 0, -1, 2, 3, 4, 5 }, 77));
        System.out.println(new P59().threeSumClosest(new int[] { -2,-3,5,-1,-4,5,-11,7,1,2,3,4,-7,-1,-2,-3,-4,-5 }, 45));
        System.out.println(new P59().threeSumClosest(new int[] {-1, 2, 1, -4}, 1));
    }
}
